\documentclass[UTF8]{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{ctex}
\usepackage{tikz}
\usepackage{texdraw}
\setlength{\parindent}{2em}

\title{作业5:堆排序和快速排序的测试与比较}

\author{唐瑞良\\ 强基工程力学 3210105852}

\begin{document}

\maketitle

\section{生成符合要求的数组}
\indent 生成数组的具体方法体现在了$random.h$的$random\_array$函数，它首先生成了一个乱序的数组，而后将前一定比例的数组元素进行了排序，由于当比例与元素数量充分大之后，在数组的其他部分出现顺序排列长度大于规定比例的长度的概率微乎其微，故忽略这种可能。从而我们得到了具有一定比例呈顺序的数组。也许我还应当让这有序序列在数组中间乃至靠后的部分出现，或者让其间断有序，甚至出现重复数据，但是我懒了。\\
\section{结果比较}
\indent 对于堆排序，其运行时间更取决于数据量，因为它首先要完成将所有数据编入堆内，最后再利用堆的性质进行排序。当数据变得逐渐有序，向堆内插入的速度也将加快，会对运行时间起到较小的提升。\\
\indent 对于快速排序，其运行速度普遍较堆排序快了一倍，并且它的运行速度与输入数据的有序程度十分相关，这是因为有序的输入可以让快速排序的“中间值寻找和区间的判定更加快速。\\
\indent 以下为测试结果：
\begin{center}
\begin{figure}
\includegraphics{Heap.PNG}
\caption{堆排序的测试结果}
\end{figure}
\begin{figure}
\includegraphics{Quick.PNG}
\caption{快速排序的测试结果}
\end{figure}
\end{center}
\section{快速排序的可能提升方案}
\begin{itemize}
\item[1)]考虑将median3升级至median5或更高，这能够帮助化解一部分median3的最坏情况从而提升效率。
\item[2)]进行更多的分区。引入等于中轴值的分区，这能避免因为重复的数据导致一直交换相同的元素。
\end{itemize}
\end{document}
